/**
 * 
 */
package at.fhhgb.mc.exercise01;

/**
 * @author ralfkralicek
 * 
 */

public class BinarySearchTree {
	int counter = 0; // to count how many elements are in the tree.

	/** Inner class for the binary tree node. **/
	protected class BinaryTreeNode {
		// the left sub node (smaller as the parent)
		private BinaryTreeNode left;
		// the right sub node (bigger than the parent)
		private BinaryTreeNode right;
		// the date saved in the node
		private int data;

		/**
		 * Constructor for the node.
		 * 
		 * @param elem
		 *            the element to put in the node
		 */
		public BinaryTreeNode(int elem) {
			data = elem;
			left = null;
			right = null;
		}

		/**
		 * Setting method to set the left sub node.
		 * 
		 * @param l
		 *            the node to set left.
		 */
		public void setLeft(BinaryTreeNode l) {
			left = l;
		}

		/**
		 * Getting method to get the left sub node.
		 * 
		 * @return the left sub node.
		 */
		public BinaryTreeNode getLeft() {
			return left;
		}

		/**
		 * Setting method to set the right node.
		 * 
		 * @param r
		 *            the right node.
		 */
		public void setRight(BinaryTreeNode r) {
			right = r;
		}

		/**
		 * Pointer to the right sub node.
		 * 
		 * @return the pointer to the right.
		 */
		public BinaryTreeNode getRight() {
			return right;
		}

		/**
		 * Setting method for the data.
		 * 
		 * @param d
		 *            the value to put in the node.
		 */
		public void setData(int d) {
			this.data = d;
		}

		/**
		 * Getting method for the data.
		 * 
		 * @return the value out of the node.
		 */
		public int getData() {
			return data;
		}
	}

	/** Root node of the tree. **/
	protected BinaryTreeNode root;
	/** Number of elements stored in the tree. */
	protected int size;

	/**
	 * Inserts the given element in the tree. Duplicate elements are not
	 * allowed.
	 * 
	 * @param elem
	 *            the given element
	 * @return true if insertion was successful, false otherwise.
	 */
	public boolean insert(int elem) {
		BinaryTreeNode current = root; // starting node is root
		return insertElem(current, elem);

	}

	/**
	 * Private insert method.
	 * 
	 * @param current
	 *            the actual node. At the begin it is ever root.
	 * @param elem
	 *            element to insert
	 * @return true if everything goes right and false when the element exists.
	 */
	private boolean insertElem(BinaryTreeNode current, int elem) {
		if (current == null) {
			BinaryTreeNode newNode = new BinaryTreeNode(elem);
			root = newNode;
			counter++; // counter for the elements
			return true;
		} else if (current.getData() == elem) {// element exists already
			return false;
		} else if (current.getData() > elem) { // left side
			if (current.getLeft() == null) {
				BinaryTreeNode newNode = new BinaryTreeNode(elem);
				current.setLeft(newNode);
				counter++;
				return true;
			} else {
				return insertElem(current.getLeft(), elem);
			}
		} else if (current.getData() < elem) { // right side
			if (current.getRight() == null) {
				BinaryTreeNode newNode = new BinaryTreeNode(elem);
				current.setRight(newNode);
				counter++;
				return true;

			} else {
				return insertElem(current.getRight(), elem);
			}
		} else {
			return false;
		}
	}

	/**
	 * Searches for the (first) element with the given key. Returns true if it
	 * could be found, false otherwise.
	 * 
	 * @param key
	 *            element we are looking for
	 * @return true if the element was found
	 */
	public boolean find(int key) {
		BinaryTreeNode current = root;
		return findKey(current, key);
	}

	/**
	 * Private searching method where current is the actual node we proof.
	 * 
	 * @param current
	 *            the actual node we are proofing
	 * @param key
	 *            the value we are looking for
	 * @return true if the element was found and false if the element was not
	 *         found.
	 */
	private boolean findKey(BinaryTreeNode current, int key) {
		if (root == null) {// empty tree
			return false;
		}

		if (current.getData() == key) {// element is found
			return true;

		} else if (current.getData() > key) { // left side
			if (current.getLeft() == null) {
				return false;

			} else {
				return findKey(current.getLeft(), key);
			}

		} else if (current.getData() < key) { // right side
			if (current.getRight() == null) {

				return false;

			} else {
				return findKey(current.getRight(), key);
			}
		}
		return false;

	}

	/**
	 * Removes the (first) element with the given key. Returns true if the key
	 * could be found, false otherwise.
	 * 
	 * @param key
	 *            element to remove
	 * @return true if the element is deleted
	 */
	public boolean remove(int key) {
		BinaryTreeNode current = root;
		if (current == null) { // empty tree
			return false;
		}

		return removeKey(current, key);
	}

	/**
	 * The private remove method.
	 * 
	 * @param current
	 *            actual node.
	 * @param key
	 *            node to delete
	 * @return true if everything goes right false if something went wrong.
	 */
	private boolean removeKey(BinaryTreeNode current, int key) {
		BinaryTreeNode nextRight = null; // the next node at the right side
		BinaryTreeNode nextLeft = null;// the next node at the left side
		BinaryTreeNode bringBack = null;// helping node to delete the node
				
		// correctly

		if(root.getData()== key){
			current=root;
			if (current.getLeft() != null) {
				bringBack = current.getRight();

				root = current.getLeft();
				if (root.getRight() == null) {
					root.setRight(bringBack);

				} else {
					current = root;
					while (current.getRight() != null) {
						current = current.getRight();
					}
					current.setRight(bringBack);
				}
			} else {
				if (current.getRight() != null) {
					root = current.getRight();
				} else {
					root = null;
				}
			}
			counter--;
			return true;
			
		}
		
		if (current.getData() > key) { // left side
			if (current.getLeft() == null) {
				return false;

			}
			if (current.getLeft().getData() == key) {
				bringBack = current.getLeft().getRight();
				current.setLeft(current.getLeft().getLeft());
				nextRight = current.getLeft(); // there was no bug i found my tests work

				while (nextRight.getRight() != null) {
					nextRight = nextRight.getRight();
				}
				nextRight.setRight(bringBack);
				counter--; // counter for the elements
				return true;
			}

		} else if (current.getData() < key) { // right side
			if (current.getRight() == null) {

				return false;

			}
			if (current.getRight().getData() == key) {
				bringBack = current.getRight().getLeft();
				current.setRight(current.getRight().getRight());
				nextLeft = current.getRight();

				while (nextLeft.getLeft() != null) {
					nextLeft = nextLeft.getLeft();
				}
				nextLeft.setLeft(bringBack);
				counter--;
				return true;

			}
		}
		return false;
	}

	/**
	 * Returns the number of elements stored in the tree.
	 * 
	 * @return the amount of elements.
	 */
	public int size() {
		if (root == null) {// empty tree
			return Integer.MIN_VALUE;
		}
		return counter;
	}

	/**
	 * Returns the elements of the tree in ascending (inorder traversal) or
	 * descending (reverse inorder traversal) order.
	 * 
	 * @param ascending
	 *            true the array is ascending sorted false is descending.
	 * @return the sorted array
	 */
	public int[] toArray(boolean ascending) {
		int[] treeArray = new int[counter];
		BinaryTreeNode current = root;
		int i = 0;

		if (root == null) { // empty tree the method returns Integer.MIN_VALUE
			treeArray = new int[1];
			treeArray[0] = Integer.MIN_VALUE;
		}

		toArray(current, treeArray, i, ascending);

		return treeArray;
	}

	/**
	 * Private toArray method.
	 * 
	 * @param current
	 *            actual node
	 * @param treeArray
	 *            the array the method writes in
	 * @param i
	 *            pointer to write in the array
	 * @param ascending
	 *            true for ascending false for descending
	 * @return the array
	 */
	private int[] toArray(BinaryTreeNode current, int[] treeArray, int i,
			boolean ascending) {

		if (current != null) {
			toArray(current.getLeft(), treeArray, i, ascending);
			if (ascending == true) { // to sort ascending
				while (treeArray[i] != 0) {

					i++;
				}
			}

			if (ascending == false) { // to sort decending
				i = treeArray.length - 1;
				while (treeArray[i] != 0) {
					i--;
				}
			}

			treeArray[i] = current.getData(); // write in the array
			toArray(current.getRight(), treeArray, i, ascending);

		}

		return treeArray;
	}

	/**
	 * Returns largest number stored in the tree.
	 * 
	 * @return the largest stored number.
	 */
	public int max() {
		if (root == null) {
			return Integer.MIN_VALUE;
		}
		BinaryTreeNode current = root;
		while (current.getRight() != null) {
			current = current.getRight();
		}
		return current.getData();
	}

	/**
	 * Returns smallest number stored in the tree.
	 * 
	 * @return the smallest stored number
	 */
	public int min() {
		if (root == null) {
			return Integer.MIN_VALUE;
		}
		BinaryTreeNode current = root;
		while (current.getLeft() != null) {
			current = current.getLeft();
		}
		return current.getData();
	}

	/** Represents the tree in a human readable form. */
	public String toString() {

		StringBuffer printOut = new StringBuffer();
		if (root == null) { // if the tree is empty the method returns a String
							// "Empty Tree"

			printOut.append("Empty Tree");
			return printOut.toString();
		}

		appendString(printOut, root, 0);
		return printOut.toString();

	}

	/**
	 * Private toString method
	 * 
	 * @param printOut
	 *            StringBuffer to return
	 * @param current
	 *            actual node
	 * @param indent
	 *            is the offset
	 */
	private void appendString(StringBuffer printOut, BinaryTreeNode current,
			int indent) {

		if (current == null)
			return;
		appendString(printOut, current.getRight(), indent + 2);
		for (int i = 0; i < indent; i++) {
			printOut.append(" ");
		}
		printOut.append(current.getData());
		printOut.append('\n');
		appendString(printOut, current.getLeft(), indent + 2);

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		BinarySearchTree tree = new BinarySearchTree();

		tree.insert(70);
		tree.insert(90);
		tree.insert(50);
		tree.insert(22);
		tree.insert(99);
		tree.insert(33);
		tree.insert(44);
		tree.insert(21);
		tree.insert(51);
		tree.insert(100);
		tree.insert(110);

		tree.toArray(false);

		System.out.print(tree.toString());

	}

}
